package org.lyc.dp;

/**
 * 打家劫舍2
 * 一个专业的小偷,计划沿街偷窃.每个房间都藏有一定的现金和防盗系统, 如果两个相邻的房屋在同一晚被盗, 则会自动报警.
 * 这里的房间围成一个圈, 第一个房间和最后一个房间是紧挨着的
 * 要求在不触发报警的情况下, 一夜之间能偷取的最大金额
 * 输入 gold = [2,3,2]
 * 输出 3
 * 偷取下标为1的
 * 输入 gold = [1,2,3,1]
 * 输出 4
 * 偷取0和2
 * 输入 gold = [1,2,3]
 * 输出 3
 * 偷取 2
 *
 * @author Liu Yicong
 * @date 2024/1/31
 */
public class ERobHouse2 {
	public static int rob(int[] gold) {
		int length = gold.length;
		if (length == 1) {
			return gold[0];
		}

		int[][] dp = new int[length][2];//dp为一个二维数组, 记录是否选取首个房间的两种情况, dp[][0]表示不选, dp[][1]表示选取
		dp[0][1] = gold[0]; //选择第一个房间
		dp[0][0] = 0; //不选第一个房间
		for (int i = 1; i < length; i++) {
			for (int j = 0; j < 2; j++) {
				// 初始情况
				if (i == 1) {
					if (j == 0) {
						dp[i][j] = gold[1];
					} else {
						dp[i][j] = gold[0];
					}
				}
				// 如果选择了第一个房间, 那么最后一个房间则不能选取
				else if (i == length - 1 && j == 1) {
					dp[i][j] = dp[i - 1][j];
				} else {
					dp[i][j] = Math.max(dp[i - 1][j], dp[i - 2][j] + gold[i]);
				}
			}

		}

		return Math.max(dp[length - 1][1], dp[length - 1][0]);
	}

	public static void main(String[] args) {
		int[] gold = {4, 1, 2, 7, 5, 3, 1};
		System.out.println(rob(gold));
	}
}
